package com.bjpowernode.java;


/**
 * @author wuyuecai
 * @create 2021-06-05 9:44
 */


public class RemoveNodeDemo {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(2);
        RemoveNode.addNode(node1);
        RemoveNode.addNode(node2);
        RemoveNode.addNode(node3);
        RemoveNode.addNode(node4);
        RemoveNode.addNode(node5);
        RemoveNode.list(RemoveNode.head);
        System.out.println("删除指定val的值之后的链表");
//        RemoveNode.removeElements(RemoveNode.head, 2);
        RemoveNode.list(RemoveNode.removeElements(RemoveNode.head, 2));

    }

}

class RemoveNode {
    public static ListNode head = new ListNode(2);

    //    public static  ListNode head = null;
    public static void addNode(ListNode newNode) {
        if (head == null) {
            System.out.println("头节点为空");
            return;
        }
        ListNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;

    }

    public static void list(ListNode head) {
        if (head == null) {
            System.out.println("头节点为空");
            return;
        }
        ListNode temp = head;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
        return;


    }

    public static ListNode removeElements(ListNode head, int val) {
        //第一种
//        if (head == null) {
//            return null;
//        }
//        if (head.next == null) {
//            if (head.val == val) {
//                return null;
//            }
//            return head;
//        }
//        ListNode temp = head;
//        while (temp.next != null) {
//            if (temp.next.val == val) {
//                temp.next = temp.next.next;
//                break;
//            }
//            temp = temp.next;
//        }
//        return removeElements(temp, val);//当temp.next == null时退出递归
//        第二种:思路：头节点可以存储值的情况，删除指定值有三种情况，1.头节点为空，直接返回空2.头节点的数据域和要查的val值相同，则使用递归直接让头节点的下一个节点变成头节点，
//        直到第三种情况，即头节点的数据域和val值不相同3.头节点的数据域和val值不相同，则使用一个辅助节点遍历链表，当找到和val相同的节点时，则temp.next = temp.next.next;同时使用continue语句跳过temp节点的后移，直到查找不到有和val值相同的节点为止，这时返回头节点就行了
//        if (head == null) {
//            return null;
//        }
//        if (head.val == val) {//如果头节点的val值==val，那么就让头节点的下一个节点作为头节点
//            return removeElements(head.next, val);
//        }
//        ListNode temp = head;
//        while (temp.next != null) {
//            if (temp.next.val == val) {
//                temp.next = temp.next.next;
//                continue;//如果找到了要删除的节点要使用continue跳过temp向后移动，因为这是temp.next就已经指向下一个节点了
//            }
//            temp = temp.next;
//        }
//        return head;
        //题解1：思路：1.使用一个辅助节点指向头节点，再使用一个辅助节点指向这个辅助节点，意思是创建两个辅助节点用于遍历原链表中包括
        //头节点的所有节点。相当于第一辅助节点成为了头节点，第二个辅助节点用于指向头节点。2.然后接按照正常的不用遍历头节点的思路进行查找与val值相同的节点


//        ListNode dummyHead = new ListNode(0);
//        dummyHead.next = head;
//
//        ListNode prev = dummyHead;
//        // 判断当前结点的后继结点是否为null
//        while (prev.next != null) {
//            // 如果当前结点的后继结点的值与给定值val相等
//            // 则需将其后继结点删除
//            if (prev.next.val == val) {
//                // 通过将当前结点后继结点的后继结点挂在当前结点之后
//                // 来删除当前结点的后继结点
//                prev.next = prev.next.next;
//            } else {
//                // 如果当前结点的后继结点的值与给定值不相等
//                // 则当前结点需要保留，因此prev向前移动一个位置
//                prev = prev.next;
//            }
//        }
//        return dummyHead.next;
//
//        题解2：递归
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;


    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}